// -*- mode:c++; tab-width:2; indent-tabs-mode:nil; c-basic-offset:2 -*-
/*
 * Copyright 2012 ZXing authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * 2012-09-19 HFN translation from Java into C++
 */

#include <zxing/pdf417/decoder/ec/ErrorCorrection.h>
#include <zxing/pdf417/decoder/ec/ModulusPoly.h>
#include <zxing/pdf417/decoder/ec/ModulusGF.h>

using std::vector;
using zxing::Ref;
using zxing::ArrayRef;
using zxing::pdf417::decoder::ec::ErrorCorrection;
using zxing::pdf417::decoder::ec::ModulusPoly;
using zxing::pdf417::decoder::ec::ModulusGF;

/**
 * <p>PDF417 error correction implementation.</p>
 *
 * <p>This <a href="http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Example">example</a>
 * is quite useful in understanding the algorithm.</p>
 *
 * @author Sean Owen
 * @see com.google.zxing.common.reedsolomon.ReedSolomonDecoder
 */


ErrorCorrection::ErrorCorrection()
        : field_(ModulusGF::PDF417_GF) {
}

void ErrorCorrection::decode(ArrayRef<int> received,
                             int numECCodewords,
                             ArrayRef<int> erasures) {
    Ref<ModulusPoly> poly(new ModulusPoly(field_, received));
    ArrayRef<int> S(new Array<int>(numECCodewords));
    bool error = false;
    for (int i = numECCodewords; i > 0; i--) {
        int eval = poly->evaluateAt(field_.exp(i));
        S[numECCodewords - i] = eval;
        if (eval != 0) {
            error = true;
        }
    }

    if (error) {

        Ref<ModulusPoly> knownErrors = field_.getOne();
        for (int i = 0; i < erasures->size(); i++) {
            int b = field_.exp(received->size() - 1 - erasures[i]);
            // Add (1 - bx) term:
            ArrayRef<int> one_minus_b_x(new Array<int>(2));
            one_minus_b_x[1] = field_.subtract(0, b);
            one_minus_b_x[0] = 1;
            Ref<ModulusPoly> term(new ModulusPoly(field_, one_minus_b_x));
            knownErrors = knownErrors->multiply(term);
        }

        Ref<ModulusPoly> syndrome(new ModulusPoly(field_, S));
        //syndrome = syndrome.multiply(knownErrors);

        vector<Ref<ModulusPoly> > sigmaOmega(
                runEuclideanAlgorithm(field_.buildMonomial(numECCodewords, 1), syndrome,
                                      numECCodewords));
        Ref<ModulusPoly> sigma = sigmaOmega[0];
        Ref<ModulusPoly> omega = sigmaOmega[1];

        //sigma = sigma.multiply(knownErrors);

        ArrayRef<int> errorLocations = findErrorLocations(sigma);
        ArrayRef<int> errorMagnitudes = findErrorMagnitudes(omega, sigma, errorLocations);

        for (int i = 0; i < errorLocations->size(); i++) {
            int position = received->size() - 1 - field_.log(errorLocations[i]);
            if (position < 0) {
                throw ReedSolomonException("Bad error location!");
            }
            received[position] = field_.subtract(received[position], errorMagnitudes[i]);
#if (defined (DEBUG)  && defined _WIN32)
            {
              WCHAR szmsg[256];
              swprintf(szmsg,L"ErrorCorrection::decode: fix @ %d, new value = %d\n",
                       position, received[position]);
              OutputDebugString(szmsg);
            }
#endif
        }
    }
}

vector <Ref<ModulusPoly>>  ErrorCorrection::runEuclideanAlgorithm(Ref<ModulusPoly> a,
                                                                  Ref<ModulusPoly> b, int R) {
    // Assume a's degree is >= b's
    if (a->getDegree() < b->getDegree()) {
        Ref<ModulusPoly> temp = a;
        a = b;
        b = temp;
    }

    Ref<ModulusPoly> rLast(a);
    Ref<ModulusPoly> r(b);
    Ref<ModulusPoly> tLast(field_.getZero());
    Ref<ModulusPoly> t(field_.getOne());

    // Run Euclidean algorithm until r's degree is less than R/2
    while (r->getDegree() >= R / 2) {
        Ref<ModulusPoly> rLastLast(rLast);
        Ref<ModulusPoly> tLastLast(tLast);
        rLast = r;
        tLast = t;

        // Divide rLastLast by rLast, with quotient in q and remainder in r
        if (rLast->isZero()) {
            // Oops, Euclidean algorithm already terminated?
            throw ReedSolomonException("Euclidean algorithm already terminated?");
        }
        r = rLastLast;
        Ref<ModulusPoly> q(field_.getZero());
        int denominatorLeadingTerm = rLast->getCoefficient(rLast->getDegree());
        int dltInverse = field_.inverse(denominatorLeadingTerm);
        while (r->getDegree() >= rLast->getDegree() && !r->isZero()) {
            int degreeDiff = r->getDegree() - rLast->getDegree();
            int scale = field_.multiply(r->getCoefficient(r->getDegree()), dltInverse);
            q = q->add(field_.buildMonomial(degreeDiff, scale));
            r = r->subtract(rLast->multiplyByMonomial(degreeDiff, scale));
        }

        t = q->multiply(tLast)->subtract(tLastLast)->negative();
    }

    int sigmaTildeAtZero = t->getCoefficient(0);
    if (sigmaTildeAtZero == 0) {
        throw ReedSolomonException("sigmaTilde = 0!");
    }

    int inverse = field_.inverse(sigmaTildeAtZero);
    Ref<ModulusPoly> sigma(t->multiply(inverse));
    Ref<ModulusPoly> omega(r->multiply(inverse));
    vector<Ref<ModulusPoly> > v(2);
    v[0] = sigma;
    v[1] = omega;
    return v;
}

ArrayRef<int> ErrorCorrection::findErrorLocations(Ref<ModulusPoly> errorLocator) {
    // This is a direct application of Chien's search
    int numErrors = errorLocator->getDegree();
    ArrayRef<int> result(new Array<int>(numErrors));
    int e = 0;
    for (int i = 1; i < field_.getSize() && e < numErrors; i++) {
        if (errorLocator->evaluateAt(i) == 0) {
            result[e] = field_.inverse(i);
            e++;
        }
    }
    if (e != numErrors) {
#if (defined (DEBUG) && defined _WIN32)
        char sz[128];
        sprintf(sz,"Error number inconsistency, %d/%d!",e,numErrors);
      throw ReedSolomonException(sz);
#else
        throw ReedSolomonException("Error number inconsistency!");
#endif
    }
#if (defined (DEBUG) && defined _WIN32)
    {
      WCHAR szmsg[256];
      swprintf(szmsg,L"ErrorCorrection::findErrorLocations: found %d errors.\n",
               e);
      OutputDebugString(szmsg);
    }
#endif
    return result;
}

ArrayRef<int> ErrorCorrection::findErrorMagnitudes(Ref<ModulusPoly> errorEvaluator,
                                                   Ref<ModulusPoly> errorLocator,
                                                   ArrayRef<int> errorLocations) {
    int i;
    int errorLocatorDegree = errorLocator->getDegree();
    ArrayRef<int> formalDerivativeCoefficients(new Array<int>(errorLocatorDegree));
    for (i = 1; i <= errorLocatorDegree; i++) {
        formalDerivativeCoefficients[errorLocatorDegree - i] =
                field_.multiply(i, errorLocator->getCoefficient(i));
    }
    Ref<ModulusPoly> formalDerivative(new ModulusPoly(field_, formalDerivativeCoefficients));

    // This is directly applying Forney's Formula
    int s = errorLocations->size();
    ArrayRef<int> result(new Array<int>(s));
    for (i = 0; i < s; i++) {
        int xiInverse = field_.inverse(errorLocations[i]);
        int numerator = field_.subtract(0, errorEvaluator->evaluateAt(xiInverse));
        int denominator = field_.inverse(formalDerivative->evaluateAt(xiInverse));
        result[i] = field_.multiply(numerator, denominator);
    }
    return result;
}

